template<class Type>
RegexpToNonFinAut<Type>::RegexpToNonFinAut(void)
{
	basic = NonFinAut<Type>(2, 0, 1);
}

template<class Type>
RegexpToNonFinAut<Type>::~RegexpToNonFinAut(void)
{
}

template<class Type>
NonFinAut<Type> RegexpToNonFinAut<Type>::build_nfa_basic(input in)
{
	basic.add_trans(0, 1, in);
	return basic;
}

template<class Type>
NonFinAut<Type> RegexpToNonFinAut<Type>::build_nfa_alter(NonFinAut<Type> nfa1, NonFinAut<Type> nfa2)
{
	// How this is done: the new nfa must contain all the states in
	// nfa1 and nfa2, plus a new initial and final states. 
	// First will come the new initial state, then nfa1's states, then
	// nfa2's states, then the new final state
	
	// make room for the new initial state
	nfa1.shift_states(1);
	
	// make room for nfa1
	nfa2.shift_states(nfa1.size);
	
	// create a new nfa and initialize it with (the shifted)nfa2
	NonFinAut<Type> new_nfa(nfa2);
	
	// nfa1's states take their places in new_nfa
	new_nfa.fill_states(nfa1);
	
	// Set new initial state and the transitions from it
	new_nfa.add_trans(0, nfa1.initial, EPS);
	new_nfa.add_trans(0, nfa2.initial, EPS);
	new_nfa.initial = 0;
	
	// Make up space for the new final state
	new_nfa.append_empty_state();
	
	// Set new final state
	//
	new_nfa.final = new_nfa.size - 1;
	new_nfa.add_trans(nfa1.final, new_nfa.final, EPS);
	new_nfa.add_trans(nfa2.final, new_nfa.final, EPS);	
	
	return new_nfa;
}

template<class Type>
NonFinAut<Type> RegexpToNonFinAut<Type>::build_nfa_concat(NonFinAut<Type> nfa1, NonFinAut<Type> nfa2)
{
	// How this is done: First will come nfa1, then nfa2 (its 
	// initial state replaced with nfa1's final state)
	nfa2.shift_states(nfa1.size - 1);
	
	// create a new nfa and initialize it with (the shifted)
	// nfa2
	NonFinAut<Type> new_nfa(nfa2);
	
	// nfa1's states take their places in new_nfa
	// note: nfa1's final state overwrites nfa2's initial state,
	// thus we get the desired merge automagically (the transition
	// from nfa2's initial state now transits from nfa1's final state)
	new_nfa.fill_states(nfa1);
	
	// set the new initial state (the final state stays nfa2's final state,
	// and was already copied)
	new_nfa.initial = nfa1.initial;
	
	return new_nfa;
}

template<class Type>
NonFinAut<Type> RegexpToNonFinAut<Type>::build_nfa_star(NonFinAut<Type> nfa)
{
	// How this is done: First will come the new initial state,
	// then nfa, then the new final state

	// make room for the new initial state
	nfa.shift_states(1);
	
	// make room for the new final state
	nfa.append_empty_state();

	// add new transitions
	nfa.add_trans(nfa.final, nfa.initial, EPS);
	nfa.add_trans(0, nfa.initial, EPS);
	nfa.add_trans(nfa.final, nfa.size - 1, EPS);
	nfa.add_trans(0, nfa.size - 1, EPS);
	
	nfa.initial = 0;
	nfa.final = nfa.size - 1;
	
	return nfa;
}

template<class Type>
NonFinAut<Type> RegexpToNonFinAut<Type>::build_nfa_plus(NonFinAut<Type> nfa)
{
	// How this is done: First will come the new initial state,
	// then nfa, then the new final state

	// make room for the new initial state
	nfa.shift_states(1);
	
	// make room for the new final state
	nfa.append_empty_state();

	// add new transitions
	nfa.add_trans(nfa.final, nfa.initial, EPS);
	nfa.add_trans(0, nfa.initial, EPS);
	nfa.add_trans(nfa.final, nfa.size - 1, EPS);
		
	nfa.initial = 0;
	nfa.final = nfa.size - 1;
	return nfa;
}